# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/12/27
# @File : 382. 链表随机节点（字节考）.py
# 实现一个函数实现保证每个节点被选的概率一样（链表十分大且长度未知）
import random
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        res = 0
        link = self.head
        i = 0
        while(link):
            if i == random.randint(0,i):# randint左闭右也闭。
                res = link.val
            i += 1
            link = link.next
        return res
"""
同理，如果要随机选择 k 个数，只要在第 i 个元素处以 k/i 的概率选择该元素，以 1 - k/i 的概率保持原有选择即可
"""